<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o, 
     (c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<title>
Structure and Interpretation 
of Computer Programs
</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title=default>
<meta name=robots content="noindex,follow">
</head>
<body>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-19.html">previous</a></span><span>, <a href="book-Z-H-21.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

<a name="%_sec_3.1"></a>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_3.1">3.1&nbsp;&nbsp;Assignment and Local State</a></h2><p>

<a name="%_idx_2836"></a><a name="%_idx_2838"></a>
We ordinarily view the world as populated by independent objects, each
of which has a state that changes over time.  An object is said to
``have state'' if its behavior is influenced by its history.  A bank
account, for example, has state in that the answer to the question
``Can I withdraw $100?''  depends upon the history of deposit and
withdrawal transactions.  We can characterize an object's state by one
or more <a name="%_idx_2840"></a><em>state variables</em>, which among them maintain enough
information about history to determine the object's current behavior.
In a simple banking system, we could characterize the state of an
account by a current balance rather than by remembering the entire
history of account transactions.<p>

In a system composed of many objects, the objects are rarely
completely independent.  Each may influence the states of others
through interactions, which serve to couple the state variables of one
object to those of other objects.  Indeed, the view that a system is
composed of separate objects is most useful when the state variables
of the system can be grouped into closely coupled subsystems that are
only loosely coupled to other subsystems.<p>


This view of a system can be a powerful framework for organizing
computational models of the system.  For such a model to be modular,
it should be decomposed into computational objects that model the
actual objects in the system.  Each computational object must have its
own <em>local state variables</em> describing the actual object's state.
Since the states of objects in the system being modeled change over
time, the state variables of the corresponding computational objects
must also change.  If we choose to model the flow of time in the
system by the elapsed time in the computer, then we must have a way to
construct computational objects whose behaviors change as our programs
run.  In particular, if we wish to model state variables by ordinary
symbolic names in the programming language, then the language must
provide an <a name="%_idx_2842"></a><em>assignment operator</em> to enable us to change the value
associated with a name.<p>

<a name="%_sec_3.1.1"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.1.1">3.1.1&nbsp;&nbsp;Local State Variables</a></h3><p>


<a name="%_idx_2844"></a><a name="%_idx_2846"></a>
<a name="%_idx_2848"></a><a name="%_idx_2850"></a>To illustrate what we mean by having a computational object with
time-varying state, let us model the situation of withdrawing money
from a bank account.  We will do this using a procedure <tt>withdraw</tt>, which takes as argument an <tt>amount</tt> to be withdrawn.
If there is enough money in the account to accommodate the withdrawal,
then <tt>withdraw</tt> should return the balance remaining after the
withdrawal.  Otherwise, <tt>withdraw</tt> should return the message <em>Insufficient funds.</em> For example, if we begin with $100 in the
account, we should obtain the following sequence of responses using
<tt>withdraw</tt>:<p>

<p><p><tt>(withdraw&nbsp;25)<br>
<i>75</i><br>
(withdraw&nbsp;25)<br>
<i>50</i><br>
(withdraw&nbsp;60)<br>
<i>&quot;Insufficient&nbsp;funds&quot;</i><br>
(withdraw&nbsp;15)<br>
<i>35</i><br>
</tt><p><p>
Observe that the expression <tt>(withdraw 25)</tt>, evaluated twice,
yields different values.  This is a new kind of behavior for a
procedure.  Until now, all our procedures could be viewed as
specifications for computing mathematical functions.  A call to a
procedure computed the value of the function applied to the given
arguments, and two calls to the same procedure with the
same arguments always produced the same result.<a name="call_footnote_Temp_321" href="#footnote_Temp_321"><sup><small>1</small></sup></a><p>

To implement <tt>withdraw</tt>, we can use a variable <tt>balance</tt> to
indicate the balance of money in the account and define <tt>withdraw</tt>
as a procedure that accesses <tt>balance</tt>.  The <tt>withdraw</tt>
procedure checks to see if <tt>balance</tt> is at least as large as the
requested <tt>amount</tt>.  If so, <tt>withdraw</tt> decrements <tt>balance</tt> by <tt>amount</tt> and returns the new value of <tt>balance</tt>.
Otherwise, <tt>withdraw</tt> returns the <em>Insufficient funds</em>
message.  Here are the definitions of <tt>balance</tt> and <tt>withdraw</tt>:<p>

<p><p><tt>(define&nbsp;balance&nbsp;100)<br>
<br>
<a name="%_idx_2858"></a>(define&nbsp;(withdraw&nbsp;amount)<br>
&nbsp;&nbsp;(if&nbsp;(&gt;=&nbsp;balance&nbsp;amount)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(begin&nbsp;(set!&nbsp;balance&nbsp;(-&nbsp;balance&nbsp;amount))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;balance)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&quot;Insufficient&nbsp;funds&quot;))<br>
</tt><p><p>
Decrementing <tt>balance</tt> is accomplished by the expression<p>

<p><p><tt>(set!&nbsp;balance&nbsp;(-&nbsp;balance&nbsp;amount))<br>
</tt><p><p>
<a name="%_idx_2860"></a><a name="%_idx_2862"></a>This uses the <tt>set!</tt> special form, whose syntax is<p>

<p><p><tt>(set!&nbsp;&lt;<em>name</em>&gt;&nbsp;&lt;<em>new-value</em>&gt;)<br>
</tt><p><p>
Here &lt;<em>name</em>&gt; is a symbol and &lt;<em>new-value</em>&gt; is any expression.  <tt>Set!</tt> changes &lt;<em>name</em>&gt; so that its value is the result obtained by
evaluating &lt;<em>new-value</em>&gt;.  In the case at hand, we are changing <tt>balance</tt> so that its new value will be the result of subtracting <tt>amount</tt> from the previous value of <tt>balance</tt>.<a name="call_footnote_Temp_322" href="#footnote_Temp_322"><sup><small>2</small></sup></a><p>

<a name="%_idx_2874"></a><a name="%_idx_2876"></a><tt>Withdraw</tt> also uses the <tt>begin</tt> special form to cause
two expressions to be evaluated
in the case where the <tt>if</tt> test is true: first decrementing <tt>balance</tt> and then returning the value of <tt>balance</tt>.  In general,
evaluating the expression<p>

<p><p><tt>(begin&nbsp;&lt;<em>exp<sub>1</sub></em>&gt;&nbsp;&lt;<em>exp<sub>2</sub></em>&gt;&nbsp;<tt>...</tt> &lt;<em>exp<sub><em>k</em></sub></em>&gt;)<br>
</tt><p><p>
causes the expressions &lt;<em>exp<sub>1</sub></em>&gt; through &lt;<em>exp<sub><em>k</em></sub></em>&gt; to be
evaluated in sequence and the value of the final expression
&lt;<em>exp<sub><em>k</em></sub></em>&gt; to be returned as the value of the entire <tt>begin</tt>
form.<a name="call_footnote_Temp_323" href="#footnote_Temp_323"><sup><small>3</small></sup></a><p>

Although <tt>withdraw</tt> works as desired, the variable
<tt>balance</tt> presents a problem.  As specified above, <tt>balance</tt>
is a name defined in the global environment and is freely accessible
to be examined or modified by any procedure.  It would be much better
if we could somehow make <tt>balance</tt> internal to <tt>withdraw</tt>, so
that <tt>withdraw</tt> would be the only procedure that could access <tt>balance</tt> directly and any other procedure could access <tt>balance</tt>
only indirectly (through calls to <tt>withdraw</tt>).  This would more
accurately model the notion that <tt>balance</tt> is a local state
variable used by <tt>withdraw</tt> to keep track of the state of the
account.<p>

We can make <tt>balance</tt> internal to <tt>withdraw</tt> by rewriting the
definition as follows:<p>

<p><p><tt><a name="%_idx_2884"></a>(define&nbsp;new-withdraw<br>
&nbsp;&nbsp;(let&nbsp;((balance&nbsp;100))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(amount)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(&gt;=&nbsp;balance&nbsp;amount)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(begin&nbsp;(set!&nbsp;balance&nbsp;(-&nbsp;balance&nbsp;amount))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;balance)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&quot;Insufficient&nbsp;funds&quot;))))<br>
</tt><p><p>
What we have done here is use <tt>let</tt> to establish an environment
with a local variable <tt>balance</tt>, bound to the initial value 100.
Within this local environment, we use <tt>lambda</tt> to create a
procedure that takes <tt>amount</tt> as an argument and behaves like our
previous <tt>withdraw</tt> procedure.  This procedure -- returned as the
result of evaluating the <tt>let</tt> expression -- is <tt>new-withdraw</tt>,
which behaves in precisely the same way as <tt>withdraw</tt> but whose
variable <tt>balance</tt> is not accessible by any other
procedure.<a name="call_footnote_Temp_324" href="#footnote_Temp_324"><sup><small>4</small></sup></a><p>

Combining <tt>set!</tt> with local variables is the general programming
technique we will use for constructing computational objects with
local state.  Unfortunately, using this technique raises a serious
problem: When we first introduced procedures, we also introduced the
substitution model of evaluation
(section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.5">1.1.5</a>) to provide an interpretation of
what procedure application means.  We said that applying a procedure
should be interpreted as evaluating the body of the procedure with the
formal parameters replaced by their values.  The trouble is that, as
soon as we introduce assignment into our language, substitution is no
longer an adequate model of procedure application.  (We will see why
this is so in section&nbsp;<a href="#%_sec_3.1.3">3.1.3</a>.)  As a
consequence, we technically have at this point no way to understand
why the <tt>new-withdraw</tt> procedure behaves as claimed above.  In
order to really understand a procedure such as <tt>new-withdraw</tt>, we
will need to develop a new model of procedure application.  In
section&nbsp;<a href="book-Z-H-21.html#%_sec_3.2">3.2</a> we will introduce such a model,
together with an explanation of <tt>set!</tt> and local variables.
First, however, we examine some variations on the theme established by
<tt>new-withdraw</tt>.<p>

The following procedure, <tt>make-withdraw</tt>, creates ``withdrawal
processors.''  The formal parameter <tt>balance</tt> in <tt>make-withdraw</tt> specifies the initial amount of money in the
account.<a name="call_footnote_Temp_325" href="#footnote_Temp_325"><sup><small>5</small></sup></a><p>

<p><p><tt><a name="%_idx_2894"></a>(define&nbsp;(make-withdraw&nbsp;balance)<br>
&nbsp;&nbsp;(lambda&nbsp;(amount)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(&gt;=&nbsp;balance&nbsp;amount)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(begin&nbsp;(set!&nbsp;balance&nbsp;(-&nbsp;balance&nbsp;amount))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;balance)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&quot;Insufficient&nbsp;funds&quot;)))<br>
</tt><p><p>
<tt>Make-withdraw</tt> can be used as follows to create two objects
<tt>W1</tt> and <tt>W2</tt>:<p>

<p><p><tt>(define&nbsp;W1&nbsp;(make-withdraw&nbsp;100))<br>
(define&nbsp;W2&nbsp;(make-withdraw&nbsp;100))<br>
(W1&nbsp;50)<br>
<i>50</i><br>
(W2&nbsp;70)<br>
<i>30</i><br>
(W2&nbsp;40)<br>
<i>&quot;Insufficient&nbsp;funds&quot;</i><br>
(W1&nbsp;40)<br>
<i>10</i><br>
</tt><p><p>
Observe that <tt>W1</tt> and <tt>W2</tt> are completely independent objects,
each with its own local state variable <tt>balance</tt>.  Withdrawals
from one do not affect the other.<p>

We can also create objects that handle deposits as well as
withdrawals, and thus we can represent simple bank accounts.  Here is
a procedure that returns a ``bank-account object'' with
a specified initial balance:<p>

<p><p><tt><a name="%_idx_2896"></a><a name="%_idx_2898"></a>(define&nbsp;(make-account&nbsp;balance)<br>
&nbsp;&nbsp;(define&nbsp;(withdraw&nbsp;amount)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(&gt;=&nbsp;balance&nbsp;amount)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(begin&nbsp;(set!&nbsp;balance&nbsp;(-&nbsp;balance&nbsp;amount))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;balance)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&quot;Insufficient&nbsp;funds&quot;))<br>
&nbsp;&nbsp;(define&nbsp;(deposit&nbsp;amount)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(set!&nbsp;balance&nbsp;(+&nbsp;balance&nbsp;amount))<br>
&nbsp;&nbsp;&nbsp;&nbsp;balance)<br>
&nbsp;&nbsp;(define&nbsp;(dispatch&nbsp;m)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(cond&nbsp;((eq?&nbsp;m&nbsp;'withdraw)&nbsp;withdraw)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((eq?&nbsp;m&nbsp;'deposit)&nbsp;deposit)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(error&nbsp;&quot;Unknown&nbsp;request&nbsp;--&nbsp;MAKE-ACCOUNT&quot;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m))))<br>
&nbsp;&nbsp;dispatch)<br>
</tt><p><p>
Each call to <tt>make-account</tt> sets up an environment with a local
state variable <tt>balance</tt>.  Within this environment, <tt>make-account</tt> defines procedures <tt>deposit</tt> and <tt>withdraw</tt>
that access <tt>balance</tt> and an additional procedure <tt>dispatch</tt>
that takes a ``message'' as input and returns one of the two local
procedures.  The <tt>dispatch</tt> procedure itself is returned as the
value that represents the bank-account object.
This is precisely the <a name="%_idx_2900"></a><em>message-passing</em>
style of programming that we saw in section&nbsp;<a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a>, although
here we are using it in conjunction with the ability to modify local
variables.<p>

<tt>Make-account</tt> can be used as follows:<p>

<p><p><tt>(define&nbsp;acc&nbsp;(make-account&nbsp;100))<br>
((acc&nbsp;'withdraw)&nbsp;50)<br>
<i>50</i><br>
((acc&nbsp;'withdraw)&nbsp;60)<br>
<i>&quot;Insufficient&nbsp;funds&quot;</i><br>
((acc&nbsp;'deposit)&nbsp;40)<br>
<i>90</i><br>
((acc&nbsp;'withdraw)&nbsp;60)<br>
<i>30</i><br>
</tt><p><p>
Each call to <tt>acc</tt> returns the locally defined <tt>deposit</tt> or
<tt>withdraw</tt> procedure, which is then applied to the specified <tt>amount</tt>.  As was the case with <tt>make-withdraw</tt>, another call to <tt>make-account</tt><p>

<p><p><tt>(define&nbsp;acc2&nbsp;(make-account&nbsp;100))<br>
</tt><p><p>
will produce a completely separate account object, which maintains its
own local <tt>balance</tt>.<p>

<p><a name="%_thm_3.1"></a>
<b>Exercise 3.1.</b>&nbsp;&nbsp;An <a name="%_idx_2902"></a><em>accumulator</em> is a procedure that is called repeatedly with a
single numeric argument and accumulates its arguments into a sum.
Each time it is called, it returns the currently accumulated sum.
Write a procedure <a name="%_idx_2904"></a><tt>make-accumulator</tt> that generates accumulators,
each maintaining an independent sum.  The input to <tt>make-accumulator</tt> should specify the initial value of the sum; for
example<p>

<p><p><tt>(define&nbsp;A&nbsp;(make-accumulator&nbsp;5))<br>
(A&nbsp;10)<br>
<i>15</i><br>
(A&nbsp;10)<br>
<i>25</i><br>
</tt><p><p>
<p><p>

<p><a name="%_thm_3.2"></a>
<b>Exercise 3.2.</b>&nbsp;&nbsp;In software-testing applications, it is useful to be able to count the
number of times a given procedure is called during the course of a
computation.  Write a procedure <a name="%_idx_2906"></a><a name="%_idx_2908"></a><a name="%_idx_2910"></a><tt>make-monitored</tt> that takes as
input a procedure, <tt>f</tt>, that itself takes one input.  The result
returned by <tt>make-monitored</tt> is a third procedure, say <tt>mf</tt>,
that keeps track of the number of times it has been called by
maintaining an internal counter.  If the input to <tt>mf</tt> is the
special symbol <tt>how-many-calls?</tt>, then <tt>mf</tt> returns the
value of the counter.  If the input is the special symbol <tt>reset-count</tt>, then <tt>mf</tt> resets the counter to zero.  For any other
input, <tt>mf</tt> returns the result of calling <tt>f</tt> on that input
and increments the counter.  For instance, we could make a monitored
version of the <tt>sqrt</tt> procedure:<p>

<p><p><tt>(define&nbsp;s&nbsp;(make-monitored&nbsp;sqrt))<br>
<br>
(s&nbsp;100)<br>
<i>10</i><br>
<br>
(s&nbsp;'how-many-calls?)<br>
<i>1</i><br>
</tt><p><p>
<p><p>

<p><a name="%_thm_3.3"></a>
<b>Exercise 3.3.</b>&nbsp;&nbsp;<a name="%_idx_2912"></a><a name="%_idx_2914"></a>Modify the <tt>make-account</tt> procedure so that it creates
password-protected accounts.  That is, <tt>make-account</tt> should take
a symbol as an additional argument, as in<p>

<p><p><tt>(define&nbsp;acc&nbsp;(make-account&nbsp;100&nbsp;'secret-password))<br>
</tt><p><p>
The resulting account object should process a request only if it is
accompanied by the password with which the account was created, and
should otherwise return a complaint:<p>

<p><p><tt>((acc&nbsp;'secret-password&nbsp;'withdraw)&nbsp;40)<br>
<i>60</i><br>
<br>
((acc&nbsp;'some-other-password&nbsp;'deposit)&nbsp;50)<br>
<i>&quot;Incorrect&nbsp;password&quot;</i><br>
</tt><p><p>
<p><p>

<p><a name="%_thm_3.4"></a>
<b>Exercise 3.4.</b>&nbsp;&nbsp;Modify the <tt>make-account</tt> procedure of
exercise&nbsp;<a href="#%_thm_3.3">3.3</a> by adding another local state
variable so that, if an account is accessed more than seven
consecutive times with an incorrect password, it invokes the procedure
<tt>call-the-cops</tt>.
<p>
<p>

<a name="%_sec_3.1.2"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.1.2">3.1.2&nbsp;&nbsp;The Benefits of Introducing Assignment</a></h3><p>


<a name="%_idx_2916"></a>
<a name="%_idx_2918"></a><a name="%_idx_2920"></a>As we shall see, introducing assignment into our programming language
leads us into a thicket of difficult conceptual issues.  Nevertheless,
viewing systems as collections of objects with local state is a
powerful technique for maintaining a modular design.  As a simple
example, consider the design of a procedure <tt>rand</tt> that, whenever
it is called, returns an integer chosen at random.<p>

<a name="%_idx_2922"></a>It is not at all clear what is meant by ``chosen at random.''  What we
presumably want is for successive calls to <tt>rand</tt> to produce a
sequence of numbers that has statistical properties of uniform
distribution.  We will not discuss methods for generating suitable
sequences here.  Rather, let us assume that we have a procedure <tt>rand-update</tt> that has the property that if we start with a given
number <em>x</em><sub>1</sub> and form<p>

<p><p><tt><em>x</em><sub>2</sub>&nbsp;=&nbsp;(rand-update&nbsp;<em>x</em><sub>1</sub>)<br>
<em>x</em><sub>3</sub>&nbsp;=&nbsp;(rand-update&nbsp;<em>x</em><sub>2</sub>)<br>
</tt><p><p>
then the sequence of values <em>x</em><sub>1</sub>, <em>x</em><sub>2</sub>, <em>x</em><sub>3</sub>, <tt>...</tt>, will have the
desired statistical properties.<a name="call_footnote_Temp_330" href="#footnote_Temp_330"><sup><small>6</small></sup></a><p>

We can implement <tt>rand</tt> as a procedure with a local state variable
<tt>x</tt> that is initialized to some fixed value <tt>random-init</tt>.
Each call to <tt>rand</tt> computes <tt>rand-update</tt> of the current
value of <tt>x</tt>, returns this as the random number, and also stores
this as the new value of <tt>x</tt>.<p>

<p><p><tt><a name="%_idx_2934"></a>(define&nbsp;rand<br>
&nbsp;&nbsp;(let&nbsp;((x&nbsp;random-init))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;()<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(set!&nbsp;x&nbsp;(rand-update&nbsp;x))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x)))<br>
</tt><p><p><p>

Of course, we could generate the same sequence of random numbers
without using assignment by simply calling <tt>rand-update</tt> directly.
However, this would mean that any part of our program that used random
numbers would have to explicitly remember the current value of <tt>x</tt>
to be passed as an argument to <tt>rand-update</tt>.  To realize what an
annoyance this would be, consider using random numbers to implement a
technique called <a name="%_idx_2936"></a><a name="%_idx_2938"></a><em>Monte Carlo simulation</em>.<p>

The Monte Carlo method consists of choosing sample experiments at
random from a large set and then making deductions on the basis of the
probabilities estimated from tabulating the results of those
experiments.  For example, we can approximate <a name="%_idx_2940"></a><img src="book-Z-G-D-9.gif" border="0"> using the fact
that 6/<img src="book-Z-G-D-9.gif" border="0"><sup>2</sup> is the probability that two integers chosen at random
will have no factors in common; that is, that their greatest common
divisor will be 1.<a name="call_footnote_Temp_331" href="#footnote_Temp_331"><sup><small>7</small></sup></a> To obtain
the approximation to <img src="book-Z-G-D-9.gif" border="0">, we perform a large number of experiments.
In each experiment we choose two integers at random and perform a test
<a name="%_idx_2946"></a>to see if their GCD is 1.  The fraction of times that the test is
passed gives us our estimate of 6/<img src="book-Z-G-D-9.gif" border="0"><sup>2</sup>, and from this we obtain our
approximation to <img src="book-Z-G-D-9.gif" border="0">.<p>

The heart of our program is a procedure <tt>monte-carlo</tt>, which takes
as arguments the number of times to try an experiment, together with
the experiment, represented as a no-argument procedure that will
return either true or false each time it is run.  <tt>Monte-carlo</tt>
runs the experiment for the designated number of trials and returns a
number telling the fraction of the trials in which the experiment was
found to be true.<p>

<p><p><tt><a name="%_idx_2948"></a>(define&nbsp;(estimate-pi&nbsp;trials)<br>
&nbsp;&nbsp;(sqrt&nbsp;(/&nbsp;6&nbsp;(monte-carlo&nbsp;trials&nbsp;cesaro-test))))<br>
<a name="%_idx_2950"></a>(define&nbsp;(cesaro-test)<br>
&nbsp;&nbsp;&nbsp;(=&nbsp;(gcd&nbsp;(rand)&nbsp;(rand))&nbsp;1))<br>
<a name="%_idx_2952"></a>(define&nbsp;(monte-carlo&nbsp;trials&nbsp;experiment)<br>
&nbsp;&nbsp;(define&nbsp;(iter&nbsp;trials-remaining&nbsp;trials-passed)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(cond&nbsp;((=&nbsp;trials-remaining&nbsp;0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(/&nbsp;trials-passed&nbsp;trials))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((experiment)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(iter&nbsp;(-&nbsp;trials-remaining&nbsp;1)&nbsp;(+&nbsp;trials-passed&nbsp;1)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(iter&nbsp;(-&nbsp;trials-remaining&nbsp;1)&nbsp;trials-passed))))<br>
&nbsp;&nbsp;(iter&nbsp;trials&nbsp;0))<br>
</tt><p><p><p>

Now let us try the same computation using <tt>rand-update</tt> directly
rather than <tt>rand</tt>, the way we would be forced to proceed if we
did not use assignment to model local state:<p>

<p><p><tt><a name="%_idx_2954"></a>(define&nbsp;(estimate-pi&nbsp;trials)<br>
&nbsp;&nbsp;(sqrt&nbsp;(/&nbsp;6&nbsp;(random-gcd-test&nbsp;trials&nbsp;random-init))))<br>
(define&nbsp;(random-gcd-test&nbsp;trials&nbsp;initial-x)<br>
&nbsp;&nbsp;(define&nbsp;(iter&nbsp;trials-remaining&nbsp;trials-passed&nbsp;x)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((x1&nbsp;(rand-update&nbsp;x)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((x2&nbsp;(rand-update&nbsp;x1)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cond&nbsp;((=&nbsp;trials-remaining&nbsp;0)&nbsp;&nbsp;&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(/&nbsp;trials-passed&nbsp;trials))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((=&nbsp;(gcd&nbsp;x1&nbsp;x2)&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(iter&nbsp;(-&nbsp;trials-remaining&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;trials-passed&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x2))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(iter&nbsp;(-&nbsp;trials-remaining&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;trials-passed<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x2))))))<br>
&nbsp;&nbsp;(iter&nbsp;trials&nbsp;0&nbsp;initial-x))<br>
</tt><p><p><p>

While the program is still simple, it betrays some painful
breaches of modularity.  In our first version of the program, using
<tt>rand</tt>, we can express the Monte Carlo method directly as
a general <tt>monte-carlo</tt> procedure that takes as an argument an
arbitrary <tt>experiment</tt> procedure.  In our second version of the
program, with no local state for the random-number generator, <tt>random-gcd-test</tt> must explicitly manipulate the random numbers <tt>x1</tt> and <tt>x2</tt> and recycle <tt>x2</tt> through the iterative loop as
the new input to <tt>rand-update</tt>.  This explicit handling of the
random numbers intertwines the structure of accumulating test results
with the fact that our particular experiment uses two random numbers,
whereas other Monte Carlo experiments might use one random number or
three.  Even the top-level procedure <tt>estimate-pi</tt> has to be
concerned with supplying an initial random number.  The fact that the
random-number generator's insides are leaking out into other parts of
the program makes it difficult for us to isolate the Monte Carlo idea
so that it can be applied to other tasks.  In the first version of the
program, assignment encapsulates the state of the random-number
generator within the <tt>rand</tt> procedure, so that the details of
random-number generation remain independent of the rest of the
program.<p>

The general phenomenon illustrated by the Monte Carlo example is this:
From the point of view of one part of a complex process, the other
parts appear to change with time.  They have hidden time-varying local
state.  If we wish to write computer programs whose structure reflects
this decomposition, we make
computational objects (such as bank accounts and random-number
generators) whose behavior changes with time.  We model state with
local state variables, and we model the changes of state with
assignments to those variables.<p>

It is tempting to conclude this discussion by saying that, by
introducing assignment and the technique of hiding state in local
variables, we are able to structure systems in a more modular fashion
than if all state had to be manipulated explicitly, by passing
additional parameters.  Unfortunately, as we shall see, the story is
not so simple.<p>

<p><a name="%_thm_3.5"></a>
<b>Exercise 3.5.</b>&nbsp;&nbsp;<a name="%_idx_2956"></a><a name="%_idx_2958"></a><a name="%_idx_2960"></a><em>Monte Carlo integration</em> is a method of estimating definite
integrals by means of Monte Carlo simulation.  Consider computing the
area of a region of space described by a predicate <em>P</em>(<em>x</em>, <em>y</em>) that is
true for points (<em>x</em>, <em>y</em>) in the region and false for points not in the
region.  For example, the region contained within a circle of radius
3 centered at (5, 7) is described by the predicate that tests
whether (<em>x</em> - 5)<sup>2</sup>  +  (<em>y</em> - 7)<sup>2</sup><u>&lt;</u> 3<sup>2</sup>.  To estimate the area of the
region described by such a predicate, begin by choosing a rectangle
that contains the region.  For example, a rectangle with diagonally
opposite corners at (2, 4) and (8, 10) contains the circle above.
The desired integral is the area of that portion of the rectangle that
lies in the region.  We can estimate the integral by picking, at
random, points (<em>x</em>,<em>y</em>) that lie in the rectangle, and testing <em>P</em>(<em>x</em>,
<em>y</em>) for each point to determine whether the point lies in the region.
If we try this with many points, then the fraction of points that fall
in the region should give an estimate of the proportion of the
rectangle that lies in the region.  Hence, multiplying this fraction
by the area of the entire rectangle should produce an estimate of the
integral.<p>

Implement Monte Carlo integration as a procedure <a name="%_idx_2962"></a><tt>estimate-integral</tt> that takes as arguments a predicate <tt>P</tt>, upper
and lower bounds <tt>x1</tt>, <tt>x2</tt>, <tt>y1</tt>, and <tt>y2</tt> for the
rectangle, and the number of trials to perform in order to produce the
estimate.  Your procedure should use the same <tt>monte-carlo</tt> procedure that was used above to estimate <img src="book-Z-G-D-9.gif" border="0">.  Use
your <tt>estimate-integral</tt> to produce an estimate of <img src="book-Z-G-D-9.gif" border="0"> by
measuring the area of a unit circle.<p>

You will find it useful to have a procedure that returns a number
chosen at random from a given range.  The following <tt>random-in-range</tt>
procedure implements this in terms of the <tt>random</tt>
procedure used in section&nbsp;<a href="book-Z-H-11.html#%_sec_1.2.6">1.2.6</a>, which returns a nonnegative
number less than its input.<a name="call_footnote_Temp_333" href="#footnote_Temp_333"><sup><small>8</small></sup></a><p>

<p><p><tt><a name="%_idx_2970"></a>(define&nbsp;(random-in-range&nbsp;low&nbsp;high)<br>
&nbsp;&nbsp;(let&nbsp;((range&nbsp;(-&nbsp;high&nbsp;low)))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;low&nbsp;(random&nbsp;range))))<br>
</tt><p><p>
<p><p>

<p><a name="%_thm_3.6"></a>
<b>Exercise 3.6.</b>&nbsp;&nbsp;<a name="%_idx_2972"></a><a name="%_idx_2974"></a>It is useful to be able to reset a random-number generator to produce
a sequence starting from a given value.  Design a new <tt>rand</tt>
procedure that is called with an argument that is either the symbol
<tt>generate</tt> or the symbol <tt>reset</tt> and behaves as follows: <tt>(rand
'generate)</tt> produces a new random number; <tt>((rand 'reset)
&lt;<em>new-value</em>&gt;)</tt> resets the internal state variable to the designated
&lt;<em>new-value</em>&gt;.  Thus, by resetting the state, one can generate
repeatable sequences.  These are very handy to have when testing and
debugging programs that use random numbers.

<p>
<p>

<a name="%_sec_3.1.3"></a>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_3.1.3">3.1.3&nbsp;&nbsp;The Costs of Introducing Assignment</a></h3><p>


<a name="%_idx_2976"></a>
As we have seen, the <tt>set!</tt> operation enables us to model objects
that have local state.  However, this advantage comes at a price.  Our
programming language can no longer be interpreted in terms of the
substitution model of procedure application that we introduced in
section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.5">1.1.5</a>.  Moreover, no simple model with
``nice'' mathematical properties can be an adequate framework for
dealing with objects and assignment in programming languages.<p>

So long as we do not use assignments, two evaluations of the same
procedure with the same arguments will produce the same result, so
that procedures can be viewed as computing mathematical functions.
Programming without any use of assignments, as we did throughout the
first two chapters of this book, is accordingly known as <a name="%_idx_2978"></a><em>functional programming</em>.<p>

<a name="%_idx_2980"></a>To understand how assignment complicates matters, consider a
simplified version of the <tt>make-withdraw</tt> procedure of
section&nbsp;<a href="#%_sec_3.1.1">3.1.1</a> that does not bother to check
for an insufficient amount:<p>

<p><p><tt><a name="%_idx_2982"></a>(define&nbsp;(make-simplified-withdraw&nbsp;balance)<br>
&nbsp;&nbsp;(lambda&nbsp;(amount)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(set!&nbsp;balance&nbsp;(-&nbsp;balance&nbsp;amount))<br>
&nbsp;&nbsp;&nbsp;&nbsp;balance))<br>
(define&nbsp;W&nbsp;(make-simplified-withdraw&nbsp;25))<br>
(W&nbsp;20)<br>
<i>5</i><br>
(W&nbsp;10)<br>
<i> - 5</i><br>
</tt><p><p>
Compare this procedure with the following <tt>make-decrementer</tt>
procedure, which does not use <tt>set!</tt>:<p>

<p><p><tt><a name="%_idx_2984"></a>(define&nbsp;(make-decrementer&nbsp;balance)<br>
&nbsp;&nbsp;(lambda&nbsp;(amount)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(-&nbsp;balance&nbsp;amount)))<br>
</tt><p><p>
<tt>Make-decrementer</tt> returns a procedure that subtracts its input
from a designated amount <tt>balance</tt>, but there is no accumulated effect
over successive calls, as with <tt>make-simplified-withdraw</tt>:<p>

<p><p><tt>(define&nbsp;D&nbsp;(make-decrementer&nbsp;25))<br>
(D&nbsp;20)<br>
<i>5</i><br>
(D&nbsp;10)<br>
<i>15</i><br>
</tt><p><p>
We can use the substitution model to explain how <tt>make-decrementer</tt> works.  For instance, let us analyze the evaluation
of the expression<p>

<p><p><tt>((make-decrementer&nbsp;25)&nbsp;20)<br>
</tt><p><p>
We first simplify the operator of the combination by substituting 25
for <tt>balance</tt> in the body of <tt>make-decrementer</tt>.  This reduces
the expression to<p>


<p><p><tt>((lambda&nbsp;(amount)&nbsp;(-&nbsp;25&nbsp;amount))&nbsp;20)<br>
</tt><p><p>
Now we apply the operator by substituting 20 for <tt>amount</tt> in the
body of the <tt>lambda</tt> expression:<p>


<p><p><tt>(-&nbsp;25&nbsp;20)<br>
</tt><p><p>
The final answer is 5.<p>

Observe, however, what happens if we attempt a similar substitution
analysis with <tt>make-simplified-withdraw</tt>:<p>


<p><p><tt>((make-simplified-withdraw&nbsp;25)&nbsp;20)<br>
</tt><p><p>
We first simplify the operator by substituting 25 for <tt>balance</tt> in
the body of <tt>make-simplified-withdraw</tt>.
This reduces the expression to<a name="call_footnote_Temp_335" href="#footnote_Temp_335"><sup><small>9</small></sup></a><p>


<p><p><tt>((lambda&nbsp;(amount)&nbsp;(set!&nbsp;balance&nbsp;(-&nbsp;25&nbsp;amount))&nbsp;25)&nbsp;20)<br>
</tt><p><p>
Now we apply the operator by substituting 20 for <tt>amount</tt> in the
body of the <tt>lambda</tt> expression:<p>


<p><p><tt>(set!&nbsp;balance&nbsp;(-&nbsp;25&nbsp;20))&nbsp;25<br>
</tt><p><p>
If we adhered to the substitution model, we would have to say that the
meaning of the procedure application is to first set <tt>balance</tt> to
5 and then return 25 as the value of the expression.  This gets the
wrong answer.  In order to get the correct answer, we would have to
somehow distinguish the first occurrence of <tt>balance</tt> (before the
effect of the <tt>set!</tt>)  from the second occurrence of <tt>balance</tt>
(after the effect of the <tt>set!</tt>), and the substitution model
cannot do this.<p>


The trouble here is that substitution is based ultimately on the
notion that the symbols in our language are essentially names for
values.  But as soon as we introduce <tt>set!</tt> and the idea that the
value of a variable can change, a variable can no longer be simply a
name.  Now a variable somehow refers to a place where a value can be
stored, and the value stored at this place can change.  In
section&nbsp;<a href="book-Z-H-21.html#%_sec_3.2">3.2</a>
we will see how environments play this role of ``place'' in our
computational model.
<p>

<a name="%_sec_Temp_336"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_336">Sameness and change</a></h4><p>

<a name="%_idx_2986"></a><a name="%_idx_2988"></a>
The issue surfacing here is more profound than the mere breakdown of a
particular model of computation.  As soon as we introduce change into
our computational models, many notions that were previously
straightforward become problematical.  Consider the concept of two
things being ``the same.''<p>

Suppose we call <tt>make-decrementer</tt> twice with the same argument to
create two procedures:<p>

<p><p><tt>(define&nbsp;D1&nbsp;(make-decrementer&nbsp;25))<br>
(define&nbsp;D2&nbsp;(make-decrementer&nbsp;25))<br>
</tt><p><p>
Are <tt>D1</tt> and <tt>D2</tt> the same?  An acceptable answer is yes,
because <tt>D1</tt> and <tt>D2</tt> have the same computational
behavior -- each is a procedure that subtracts its input from 25.  In
fact, <tt>D1</tt> could be substituted for <tt>D2</tt> in any computation
without changing the result.<p>

Contrast this with making two calls to <tt>make-simplified-withdraw</tt>:<p>

<p><p><tt>(define&nbsp;W1&nbsp;(make-simplified-withdraw&nbsp;25))<br>
(define&nbsp;W2&nbsp;(make-simplified-withdraw&nbsp;25))<br>
</tt><p><p>
Are <tt>W1</tt> and <tt>W2</tt> the same?  Surely not, because calls to <tt>W1</tt> and <tt>W2</tt> have distinct effects, as shown by the following
sequence of interactions:<p>

<p><p><tt>(W1&nbsp;20)<br>
<i>5</i><br>
(W1&nbsp;20)<br>
<i> - 15</i><br>
(W2&nbsp;20)<br>
<i>5</i><br>
</tt><p><p>
Even though <tt>W1</tt> and <tt>W2</tt> are ``equal'' in the sense that they
are both created by evaluating the same expression, <tt>(make-simplified-withdraw&nbsp;25)</tt>, it is not true that <tt>W1</tt> could be
substituted for <tt>W2</tt> in any expression without changing the result
of evaluating the expression.<p>

A language that supports the concept that ``equals can be substituted
for equals'' in an expresssion
without changing the value of the expression is said to be
<a name="%_idx_2990"></a><a name="%_idx_2992"></a><a name="%_idx_2994"></a><em>referentially transparent</em>.  Referential transparency is violated
when we include <tt>set!</tt> in our computer language.  This makes it
tricky to determine when we can simplify expressions by substituting
equivalent expressions.  Consequently, reasoning about programs that
use assignment becomes drastically more difficult.<p>

Once we forgo referential transparency, the notion of what it means
for computational objects to be ``the same'' becomes difficult to
capture in a formal way.  Indeed, the meaning of ``same'' in the real
world that our programs model is hardly clear in itself.  In general,
we can determine that two apparently identical objects are indeed
``the same one'' only by modifying one object and then observing
whether the other object has changed in the same way.  But how can we
tell if an object has ``changed'' other than by observing the ``same''
object twice and seeing whether some property of the object differs
from one observation to the next?  Thus, we cannot determine
``change'' without some <em>a priori</em> notion of ``sameness,'' and we
cannot determine sameness without observing the effects of change.<p>

<a name="%_idx_2996"></a>As an example of how this issue arises in programming, consider the
situation where Peter and Paul have a bank account with $100 in
it.  There is a substantial difference between modeling this as<p>

<p><p><tt>(define&nbsp;peter-acc&nbsp;(make-account&nbsp;100))<br>
(define&nbsp;paul-acc&nbsp;(make-account&nbsp;100))<br>
</tt><p><p>
and modeling it as<p>

<p><p><tt>(define&nbsp;peter-acc&nbsp;(make-account&nbsp;100))<br>
(define&nbsp;paul-acc&nbsp;peter-acc)<br>
</tt><p><p>
In the first situation, the two bank accounts are distinct.
Transactions made by Peter will not affect Paul's account, and vice
versa.  In the second situation, however, we have defined <tt>paul-acc</tt> to be <em>the same thing</em> as <tt>peter-acc</tt>.  In effect,
Peter and Paul now have a joint bank account, and if Peter makes a
withdrawal from <tt>peter-acc</tt> Paul will observe less money in <tt>paul-acc</tt>.  These two similar but distinct situations can cause
confusion in building computational models.  With the shared account,
in particular, it can be especially confusing that there is one object
(the bank account) that has two different names (<tt>peter-acc</tt> and
<tt>paul-acc</tt>); if we are searching for all the places in our program
where <tt>paul-acc</tt> can be changed, we must remember to look also at
things that change <tt>peter-acc</tt>.<a name="call_footnote_Temp_337" href="#footnote_Temp_337"><sup><small>10</small></sup></a><p>


With reference to the above remarks on ``sameness'' and ``change,''
observe that if Peter and Paul could only examine their bank balances,
and could not perform operations that changed the balance, then the
issue of whether the two accounts are distinct would be moot.  In
general, so long as we never modify data objects, we can regard a
compound data object to be precisely the totality of its pieces.  For
example, a rational number is determined by giving its numerator and
its denominator.  But this view is no longer valid in the presence of
change, where a compound data object has an ``identity'' that is
something different from the pieces of which it is composed.  A bank
account is still ``the same'' bank account even if we change the
balance by making a withdrawal; conversely, we could have two
different bank accounts with the same state information.  This
complication is a consequence, not of our programming language, but of
our perception of a bank account as an object.  We do not, for
example, ordinarily regard a rational number as a changeable object
with identity, such that we could change the numerator and still have
``the same'' rational number.

<a name="%_sec_Temp_338"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_338">Pitfalls of imperative programming</a></h4><p>

In contrast to functional programming, programming that makes
extensive use of assignment is known as <a name="%_idx_3014"></a><a name="%_idx_3016"></a><em>imperative
programming</em>.  In addition to raising complications about
computational models, programs written in imperative style are
susceptible to bugs that cannot occur in functional programs.  For
example, recall the iterative factorial program from
section&nbsp;<a href="book-Z-H-11.html#%_sec_1.2.1">1.2.1</a>:

<p><p><tt>(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;(define&nbsp;(iter&nbsp;product&nbsp;counter)<br>
&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;counter&nbsp;n)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;product<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(iter&nbsp;(*&nbsp;counter&nbsp;product)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;counter&nbsp;1))))<br>
&nbsp;&nbsp;(iter&nbsp;1&nbsp;1))<br>
</tt><p><p>
Instead of passing arguments in the internal iterative loop, we could
adopt a more imperative style by using explicit assignment
to update the values of the variables <tt>product</tt> and <tt>counter</tt>:
<p><p><tt><a name="%_idx_3018"></a>(define&nbsp;(factorial&nbsp;n)<br>
&nbsp;&nbsp;(let&nbsp;((product&nbsp;1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(counter&nbsp;1))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(define&nbsp;(iter)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;counter&nbsp;n)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;product<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(begin&nbsp;(set!&nbsp;product&nbsp;(*&nbsp;counter&nbsp;product))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(set!&nbsp;counter&nbsp;(+&nbsp;counter&nbsp;1))<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(iter))))<br>
&nbsp;&nbsp;&nbsp;&nbsp;(iter)))<br>
</tt><p><p>
<a name="%_idx_3020"></a><a name="%_idx_3022"></a>This does not change the results produced by the program, but it does
introduce a subtle trap.  How do we decide the order of the assignments?
As it happens, the program is correct as written.  But
writing the assignments in the opposite order
<p><p><tt>(set!&nbsp;counter&nbsp;(+&nbsp;counter&nbsp;1))<br>
(set!&nbsp;product&nbsp;(*&nbsp;counter&nbsp;product))<br>
</tt><p><p>
would have produced a different, incorrect result.
In general, programming with assignment forces us to
carefully consider the relative orders of the assignments to make sure
that each statement is using the correct version of the variables that
have been changed.  This issue simply does not arise in functional
programs.<a name="call_footnote_Temp_339" href="#footnote_Temp_339"><sup><small>11</small></sup></a>

The complexity of imperative programs becomes even worse if we
consider applications in which several processes execute concurrently.  We
will return to this in section&nbsp;<a href="book-Z-H-23.html#%_sec_3.4">3.4</a>.
First, however, we will address the issue of providing a computational
model for expressions that involve assignment, and explore the uses of
objects with local state in designing simulations.<p>

<p><a name="%_thm_3.7"></a>
<b>Exercise 3.7.</b>&nbsp;&nbsp;<a name="%_idx_3026"></a>Consider the bank account objects created by <tt>make-account</tt>, with
the password modification described in
exercise&nbsp;<a href="#%_thm_3.3">3.3</a>.  Suppose that our banking
system requires the ability to make joint accounts.  Define a
procedure <a name="%_idx_3028"></a><tt>make-joint</tt> that accomplishes this.  <tt>Make-joint</tt>
should take three arguments.  The first is a password-protected
account.  The second argument must match the password with which the
account was defined in order for the <tt>make-joint</tt> operation to
proceed.  The third argument is a new password.  <tt>Make-joint</tt> is
to create an additional access to the original account using the new
password.  For example, if <tt>peter-acc</tt> is a bank account with
password <tt>open-sesame</tt>, then<p>

<p><p><tt>(define&nbsp;paul-acc<br>
&nbsp;&nbsp;(make-joint&nbsp;peter-acc&nbsp;'open-sesame&nbsp;'rosebud))<br>
</tt><p><p>
will allow one to make transactions on <tt>peter-acc</tt> using the name
<tt>paul-acc</tt> and the password <tt>rosebud</tt>.  You may wish to modify
your solution to exercise&nbsp;<a href="#%_thm_3.3">3.3</a> to accommodate
this new feature.
<p><p>

<p><a name="%_thm_3.8"></a>
<b>Exercise 3.8.</b>&nbsp;&nbsp;<a name="%_idx_3030"></a><a name="%_idx_3032"></a>When we defined the evaluation model in
section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.3">1.1.3</a>, we said that the first step
in evaluating an expression is to evaluate its subexpressions.  But we
never specified the order in which the subexpressions should be
evaluated (e.g., left to right or right to left).  When we introduce
assignment, the order in which the arguments to a procedure are
evaluated can make a difference to the result.  Define a simple
procedure <tt>f</tt> such that evaluating <tt>(+ (f 0) (f 1))</tt> will
return 0 if the arguments to <tt>+</tt> are evaluated from left to right
but will return 1 if the arguments are evaluated from right to left.

<p>
<p>

<p><div class=smallprint><hr></div><p>
<div class=footnote><p><a name="footnote_Temp_321" href="#call_footnote_Temp_321"><sup><small>1</small></sup></a> Actually,
this is not quite true.  One exception was the <a name="%_idx_2852"></a><a name="%_idx_2854"></a>random-number generator
in section&nbsp;<a href="book-Z-H-11.html#%_sec_1.2.6">1.2.6</a>.  Another exception involved the
<a name="%_idx_2856"></a>operation/type tables we introduced in section&nbsp;<a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a>,
where the values of two calls to <tt>get</tt> with the same arguments
depended on intervening calls to <tt>put</tt>.
On the other hand, until we introduce
assignment, we have no way to create such procedures ourselves.

<p><a name="footnote_Temp_322" href="#call_footnote_Temp_322"><sup><small>2</small></sup></a> <a name="%_idx_2864"></a><a name="%_idx_2866"></a>The value of a <tt>set!</tt> expression is implementation-dependent.
<tt>Set!</tt> should be used only for its effect, not for its value.<p>

<a name="%_idx_2868"></a><a name="%_idx_2870"></a><a name="%_idx_2872"></a>The name
<tt>set!</tt> reflects a naming convention used in Scheme: Operations
that change the values of variables (or that change data structures,
as we will see in section&nbsp;<a href="book-Z-H-22.html#%_sec_3.3">3.3</a>) are given names that
end with an exclamation point.  This is similar to the convention of
designating predicates by names that end with a question mark.

<p><a name="footnote_Temp_323" href="#call_footnote_Temp_323"><sup><small>3</small></sup></a> We have already used <a name="%_idx_2878"></a><tt>begin</tt> implicitly in our
programs, because in Scheme the body of a procedure can be a sequence
of expressions.  Also, the &lt;<em>consequent</em>&gt; part of each clause in a
<a name="%_idx_2880"></a><a name="%_idx_2882"></a><tt>cond</tt> expression can be a sequence of expressions rather than a
single expression.

<p><a name="footnote_Temp_324" href="#call_footnote_Temp_324"><sup><small>4</small></sup></a> In programming-language jargon, the variable <tt>balance</tt> is said to be <a name="%_idx_2886"></a><a name="%_idx_2888"></a><em>encapsulated</em> within the <tt>new-withdraw</tt> procedure.  Encapsulation reflects the general
system-design principle known as the <a name="%_idx_2890"></a><a name="%_idx_2892"></a><em>hiding principle</em>: One can
make a system more modular and robust by protecting parts of the
system from each other; that is, by providing information access only
to those parts of the system that have a ``need to know.''

<p><a name="footnote_Temp_325" href="#call_footnote_Temp_325"><sup><small>5</small></sup></a> In contrast with <tt>new-withdraw</tt> above, we do not
have to use <tt>let</tt> to make <tt>balance</tt> a local variable, since
formal parameters are already local.  This will be clearer after the
discussion of the environment model of evaluation in section&nbsp;<a href="book-Z-H-21.html#%_sec_3.2">3.2</a>.
(See also exercise&nbsp;<a href="book-Z-H-21.html#%_thm_3.10">3.10</a>.)

<p><a name="footnote_Temp_330" href="#call_footnote_Temp_330"><sup><small>6</small></sup></a> One common way to implement
<tt>rand-update</tt> is to use the rule that <em>x</em> is updated to <em>a</em><em>x</em> + <em>b</em>
modulo <em>m</em>, where <em>a</em>, <em>b</em>, and <em>m</em> are appropriately chosen integers.
Chapter&nbsp;3 of <a name="%_idx_2924"></a>Knuth 1981 includes an extensive discussion of techniques
for generating sequences of random numbers and establishing their
statistical properties.  Notice that the <tt>rand-update</tt> procedure
computes a mathematical function: Given the same input twice, it
produces the same output.  Therefore, the number sequence produced by
<tt>rand-update</tt> certainly is not ``random,'' if by ``random'' we
insist that each number in the sequence is unrelated to the preceding
number.  The relation between ``real randomness'' and so-called <a name="%_idx_2926"></a><em>pseudo-random</em> sequences, which are produced by well-determined
computations and yet have suitable statistical properties, is a
complex question involving difficult issues in mathematics and
philosophy.  <a name="%_idx_2928"></a><a name="%_idx_2930"></a><a name="%_idx_2932"></a>Kolmogorov, Solomonoff, and Chaitin have made great
progress in clarifying these issues; a discussion can be found in
Chaitin 1975.

<p><a name="footnote_Temp_331" href="#call_footnote_Temp_331"><sup><small>7</small></sup></a> This theorem is due to E. <a name="%_idx_2942"></a>Ces&agrave;ro.  See
section 4.5.2 of <a name="%_idx_2944"></a>Knuth 1981 for a discussion and a proof.

<p><a name="footnote_Temp_333" href="#call_footnote_Temp_333"><sup><small>8</small></sup></a> <a name="%_idx_2964"></a>MIT Scheme provides such a procedure.  If <a name="%_idx_2966"></a><a name="%_idx_2968"></a><tt>random</tt>
is given an exact
integer (as in section&nbsp;<a href="book-Z-H-11.html#%_sec_1.2.6">1.2.6</a>) it returns an exact integer,
but if it is given a decimal value (as in this exercise) it returns
a decimal value.

<p><a name="footnote_Temp_335" href="#call_footnote_Temp_335"><sup><small>9</small></sup></a> We don't substitute for
the occurrence of <tt>balance</tt> in the <tt>set!</tt> expression because
the &lt;<em>name</em>&gt; in a <tt>set!</tt> is not evaluated.
If we did substitute for it, we would get
<tt>(set!&nbsp;25&nbsp;(-&nbsp;25&nbsp;amount))</tt>, which makes no sense.

<p><a name="footnote_Temp_337" href="#call_footnote_Temp_337"><sup><small>10</small></sup></a> The phenomenon of a
single computational object being accessed by more than one name is
known as <a name="%_idx_2998"></a><em>aliasing</em>.  The joint bank account situation illustrates
a very simple example of an alias.  In section&nbsp;<a href="book-Z-H-22.html#%_sec_3.3">3.3</a>
we will see much more complex examples, such as ``distinct'' compound
data structures that share parts.  Bugs can occur in our programs if
<a name="%_idx_3000"></a><a name="%_idx_3002"></a><a name="%_idx_3004"></a>we forget that a change to an object may also, as a ``side effect,''
change a ``different'' object because the two ``different'' objects
are actually a single object appearing under different aliases.  These
so-called <em>side-effect bugs</em> are so difficult to locate and to
analyze that some people have proposed that programming languages be
designed in such a way as to not allow side effects or aliasing
<a name="%_idx_3006"></a><a name="%_idx_3008"></a><a name="%_idx_3010"></a><a name="%_idx_3012"></a>(Lampson et al. 1981; Morris, Schmidt, and Wadler 1980).

<p><a name="footnote_Temp_339" href="#call_footnote_Temp_339"><sup><small>11</small></sup></a> In view of this, it is ironic that introductory programming
is most often taught in a highly imperative style.  This may be a
vestige of a belief, common throughout the 1960s and 1970s, that
programs that call procedures must inherently be less efficient than
programs that perform assignments.  (Steele (1977) <a name="%_idx_3024"></a>debunks this
argument.)  Alternatively it may reflect a view that step-by-step
assignment is easier for beginners to visualize than procedure call.
Whatever the reason, it often saddles beginning programmers with
``should I set this variable before or after that one'' concerns that can
complicate programming and obscure the important ideas.

</div>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-19.html">previous</a></span><span>, <a href="book-Z-H-21.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

</body>
</html>
